﻿# Raycaster.py: ray-casting module
# 26/05/09
# Copyright(c) 2009 Victor Freire e Cássio Espindola. All rights reserved.
# Python 2.6.2
# Version 0.02

import math
import pygame
import copy
import os
from warnings import *
#from pygame.locals import *

# Coordinate System
#
#  0 - - - - - - - >  X
#  |
#  |
#  |
#  |
#  |
#  V
#
#  Y

# NOTE: X actually represents the COLUMNS and Y the LINES, so to access the desired point the world we use:
# world[y][x] - (x and y being in matrix(grid) notation)

# ASSERTS: optimization, compile with -O (only asserts removed) or -OO(asserts and doc strings removed) flags


##class BreakPoint(Exception):
##    pass
##
##def BP(string):
##    raise BreakPoint, string
##
###TODO: figure out warnings module
##def warn(string):
##    print string


class RendererClass:
    def __init__(self, screen_width=320, screen_height=200):
        # The projection plane
        self.SCREEN_WIDTH = screen_width
        self.SCREEN_HEIGHT = screen_height

        # World constants
        self.CUBE_SIZE = self.SCREEN_WIDTH/5  # size of the world's cubes
        self.PLAYER_HEIGHT = self.CUBE_SIZE/2
        self.FOV = 60.0  # field of view

        self.SCREEN_DISTANCE = self.SCREEN_WIDTH/(2*math.tan(math.radians(self.FOV/2))) # distance to projection plane
        self.ANGLE_BETWEEN_RAYS = self.FOV/self.SCREEN_WIDTH   # angle between subsequent rays

        self.SLICE_HEIGHT_CONSTANT = self.CUBE_SIZE * self.SCREEN_DISTANCE #constant used in the slice height calculation
        self.SLICE_COLOR = (0, 0, 255)
            
        self.world = []
        self.world_bounds = (0, 0)

        # code to help debugging the renderer
        self.grid_surface_enabled = False
        self.grid_surface = None
        self.grid_scale = 1
        self.grid_wall_color = (255, 0, 0)

        self.store_ray_debug_info = False
        self.rays_info = ''        
        
        assert isinstance(self.FOV, float)
        assert isinstance(self.ANGLE_BETWEEN_RAYS, float)
        assert self.ANGLE_BETWEEN_RAYS
       

    def get_screen_size(self):
        ''' Gets the size of the rendering screen. '''
        return (SCREEN_WIDTH, SCREEN_HEIGHT)


    def toggle_ray_debug_info(self, enable):
        self.store_ray_debug_info = True if enable else False
        

    def toggle_grid_surface(self, enable):
        ''' Toggles the creation of a grid surface during each scene. '''
        if enable and not self.grid_surface_enabled:
            self.grid_surface_enabled = True
            return True
        self.grid_surface_enabled = False
        self.grid_surface = None
        return False
    
    
    def set_grid_scale(self, scale):
        ''' Sets a new scale for the world grid. '''
        if not self.grid_surface_enabled: warn("Warning: grid surface not enabled!")
        self.gridscale = scale
        

    def draw_point_grid(self, pos):
        ''' Draws a point on the 2D grid of the world. '''
        if not self.grid_surface:
            warn("Warning: tried to draw point to grid when it was not requested!")
            return False
        self.grid_surface.fill((255,0,0), (pos[0], pos[1], 1, 1))
        return True


    def draw_ray_grid(self, pov, pos):
        ''' Draws a ray from the player's on the 2D grid of the world. '''
        if not self.grid_surface:
            warn("Warning: tried to draw ray to grid when it was not requested!")
            return False
        pygame.draw.line(self.grid_surface, (0, 0, 255) , (pov.x, pov.y), (pos[0], pos[1]))
        return True
        

    
    def create_world_grid(self):
        ''' Creates a 2D grid of the world. '''
        if not self.grid_surface:
            self.grid_surface = pygame.surface.Surface((self.CUBE_SIZE * self.world_bounds[0],
                                                        self.CUBE_SIZE * self.world_bounds[1])).convert()
        self.grid_surface.fill((0,0,0))  #clears grid_surface
        for x in xrange(self.world_bounds[0]):
            for y in xrange(self.world_bounds[1]):
                newrect = pygame.rect.Rect(x * self.CUBE_SIZE,
                                           y * self.CUBE_SIZE,
                                           self.CUBE_SIZE, self.CUBE_SIZE)
                if world[y][x] > 0:
                    pygame.draw.rect(self.grid_surface, (255,255,255), newrect, 1)
                    boxrect = pygame.rect.Rect(x * self.CUBE_SIZE + 1,
                                               y * self.CUBE_SIZE + 1,
                                               self.CUBE_SIZE - 2,
                                               self.CUBE_SIZE - 2)
                    self.grid_surface.fill(self.grid_wall_color, boxrect)
                    
                else:
                    pygame.draw.rect(self.grid_surface, (255,255,255), newrect, 1)
        
        
    
    def set_screen_size(self, size):
        '''Sets the size of the rendering screen '''
        self.SCREEN_WIDTH = size[0]
        self.SCREEN_HEIGHT = size[1]
    
       
    def load_world(self, new_world):
        ''' Loads a new world matrix, returns False on error '''
        self.world = copy.deepcopy(new_world)
        self.world_bounds = (len(new_world[0]), len(new_world)) # maximum grid X and Y
        return True


    def is_valid_grid(self, gridpos):
        ''' Is the grid passed valid? '''
        return 0 <= gridpos[0] < self.world_bounds[0] and 0 <= gridpos[1] < self.world_bounds[1]

        
    def togrid(self, pos):
        ''' Converts from unit coordinate to grid coordinate '''
        return int(pos[0] / self.CUBE_SIZE), int(pos[1] / self.CUBE_SIZE)

    
    def wall_on(self, gridpos):
        ''' Checks for wall on grid coordinates X and Y '''
        return self.world[gridpos[1]][gridpos[0]]
    

    def nearest_point(self, pov, angle, h_intersect, v_intersect):
        ''' Returns the nearest point of the two and the distance to it. '''
        if h_intersect:
            h_dist = abs((pov.x - h_intersect[0]) / math.cos(math.radians(angle)))
        if v_intersect:
            v_dist = abs((pov.x - v_intersect[0]) / math.cos(math.radians(angle)))
        
        if h_intersect and v_intersect:
            if h_dist < v_dist:
                v_intersect = None
            else:
                h_intersect = None
        
        if h_intersect:
            nearest_point = h_intersect
            true_dist = h_dist
        elif v_intersect:
            nearest_point = v_intersect
            true_dist = v_dist
        
        return (nearest_point, true_dist)
    
    
    def wall_distance(self, pov, angle, h_intersect, v_intersect):
        ''' Returns the distance to a wall. '''
        # Calculates the true distance then corrects the "fishbowl" distortion
        if not (h_intersect or v_intersect):
            return None

        nearest_point, true_distance = self.nearest_point(pov, angle, h_intersect, v_intersect)

        if self.grid_surface:   
            self.draw_ray_grid(pov, nearest_point)

        # fishbowl effect correction
        angle_view_and_ray = (pov.angle - angle) % 360  #angle between the view angle and the ray
        correct_distance = abs(true_distance * math.cos(math.radians(angle_view_and_ray)))
        
        #if 90 < angle < 92:
        #    print "a"
        
        return correct_distance


    def slice_height(self, distance):
        ''' Returns the height of a wall slice based on the distance to it. '''
        if not distance: return self.CUBE_SIZE
        return self.SLICE_HEIGHT_CONSTANT / distance
    
                             
    def render_scene(self, dest, pov):
        '''
        Renders map to a surface

        dest - surface to draw on
        pov - player point of view
        '''
        
        assert self.world, "Tried to render a scene without loading the world first!"
        assert self.world_bounds[0], "Invalid world_bounds[0]"
        assert self.world_bounds[1], "Invalid world_bounds[1]"
        
        somethingdraw = False

        if self.store_ray_debug_info:
            self.rays_info = 'player view angle: %f\n' % pov.angle
            
        if self.grid_surface_enabled: self.create_world_grid()
        
        ray_angle = pov.angle + (self.FOV/2)

        if self.store_ray_debug_info:
            self.rays_info = 'player view angle: %f\n' % pov.angle
            self.rays_info += 'first original ray angle: %f\n' % ray_angle
        
        # Scan screen left to right
        for x in xrange(self.SCREEN_WIDTH):   
            # TODO: INCOMPLETE SCAN LOOP!!!

            # IMPORTANT: even though we're dealing with angles from 0-360, angles>360 are not interpreted as we may think
            # Erratic behaviour succeeds with angles higher than 360, e.g: math.radians(28) != math.radians(388)
            # This line below only works due to Python's characteristic remainder behaviour, for other languages such as
            # C++ use if ray_angle < 0: ray_angle += 360 else ray_angle %= 360
            ray_angle %= 360  

            h_hit = self.horizontal_intersect((pov.x, pov.y), ray_angle)
            v_hit = self.vertical_intersect((pov.x, pov.y), ray_angle)
                    
            #DEBUG
            if self.store_ray_debug_info:
                self.rays_info += '%d - %f:\n ' % (x, ray_angle)
                if h_hit: self.rays_info += 'h_hit (%d, %d) -- ' % h_hit
                if v_hit: self.rays_info += 'v_hit (%d, %d)    ' % v_hit
                self.rays_info += '\n'                            
            
            wall_dist = self.wall_distance(pov, ray_angle, h_hit, v_hit)

            #DEBUG
            if wall_dist:
                somethingdraw = True
                # Calculate slice parameters
                slice_h = self.slice_height(wall_dist)
                slice_y1 = (self.SCREEN_HEIGHT - slice_h)/2
                slice_y2 = slice_y1 + slice_h
                
                # Finally, draw the slice on the screen
                pygame.draw.line(dest, self.SLICE_COLOR, (x, slice_y1), (x, slice_y2))
                            
            ray_angle -= self.ANGLE_BETWEEN_RAYS

        if not somethingdraw: warn("Warning: No walls were drawn!")
        return True

    
    def vertical_intersect(self, pos, ray_angle):
        '''
        Returns vertical intersection  

        pos - tuple with player's x and y position
        ray_angle - current ray angle
        '''
        
        # * integer casts are for rounding down
        # There's no intersection if the ray is parallel to the vertical grid lines
##        if ray_angle 90), dblcmp(ray_angle, 270)): return None
##        if self.double_compare(ray_angle, 90): return None
##        if self.double_compare(ray_angle, 270): return None
##                
        
        ray_facing_left = (90 < ray_angle < 270)
        ray_angle_rad = math.radians(ray_angle)

        # Finds the X of the first intersection point, then decides whether line belongs to left or right block, do not remove round down
        first_point_x = int(pos[0] / self.CUBE_SIZE) * self.CUBE_SIZE
        if ray_facing_left:
            first_point_x -= 1                  #belongs to left block
        else:
            first_point_x += self.CUBE_SIZE     #belongs to right block
        
        # Player Y plus the its distance to first intersection point, rounded down
        first_point_y_var = ( (pos[0] - first_point_x) * math.tan(ray_angle_rad) )
        first_point_y = int(pos[1] + first_point_y_var)
        
        # Is the first intersection point inside the world?
        if not self.is_valid_grid(self.togrid((first_point_x, first_point_y))):
            return None

        # If there's a wall on the first point hit, return the position else continue searching for walls
        if self.wall_on(self.togrid((first_point_x, first_point_y))): return (first_point_x, first_point_y)
        
        # Distance between subsequent intersection points
        # A MINUS HERE SINCE THE Y is inverted from cartesian, either form breaks in certain situations
        #DEBUGNOTE the minus seems correct problem might be in the horizontal intersect

        # The y variation for the next intersections must have the same sign as the first point y variation
        y_variation = abs(int(self.CUBE_SIZE * math.tan(ray_angle_rad)))
        if first_point_y_var < 0:
            y_variation = -y_variation

        if ray_facing_left:
            x_variation = -self.CUBE_SIZE 
        else:
            x_variation = self.CUBE_SIZE
        
        # Search for a intersection point until grid index is out of bounds
        last_point = (first_point_x, first_point_y) 
        while 1:
            next_point = (last_point[0] + x_variation, last_point[1] + y_variation)
            next_point_grid = self.togrid(next_point)
            
            if not self.is_valid_grid(next_point_grid):
                return None # reached end of the world without finding any walls

            if self.wall_on(next_point_grid):
                return next_point
            
            # This intersection point does not belong to a wall, proceed to next
            last_point = next_point

        
        assert 0, "Should not reach this point!"
    
    
    def horizontal_intersect(self, pos, ray_angle):
        '''
        Returns horizontal intersection  

        pos - tuple with player's x and y position
        ray_angle - current ray angle
        '''

        # * integer casts are for rounding down

        # There's no intersection if the ray is parallel to the horizontal grid lines
        if ray_angle in (0, 180):  return None
        
        ray_facing_up = (0 < ray_angle < 180)
        ray_angle_rad = math.radians(ray_angle)
        
        # Finds the Y of the first intersection point, then decides whether line belongs to upper or lower block, do not remove round down
        first_point_y = int(pos[1] / self.CUBE_SIZE) * self.CUBE_SIZE

        if ray_facing_up:
            first_point_y -= 1                   #belongs to upper block
        else:
            first_point_y += self.CUBE_SIZE      #belongs to lower block
        
        # Player X plus its the distance to first intersection point, rounded down
        first_point_x_var =  ( (pos[1] - first_point_y) / math.tan(ray_angle_rad) )
        first_point_x = int(pos[0] + first_point_x_var)
        
        # Is the first intersection point inside the world?
        if not self.is_valid_grid(self.togrid((first_point_x, first_point_y))):
            return None
                                
        # If there's a wall on the first point hit, return the position else continue searching for walls
        if self.wall_on(self.togrid((first_point_x, first_point_y))): return (first_point_x, first_point_y)

        # Distance between subsequent intersection points
        #DEBUG: analyzing the sign of the x_variation, is it really NEGATIVE and not positive as described in the text?
        
        x_variation = abs(int(self.CUBE_SIZE / math.tan(ray_angle_rad)))
        if first_point_x_var < 0: #the sign of the 2nd variation MUST be the same as the 1st!
            x_variation = -x_variation

        if ray_facing_up:
            y_variation = -self.CUBE_SIZE 
        else:
            y_variation = self.CUBE_SIZE

        # Search for a intersection point until grid index is out of bounds
        last_point = (first_point_x, first_point_y) 
        while 1:
            next_point = (last_point[0] + x_variation, last_point[1] + y_variation)
            next_point_grid = self.togrid(next_point)

            if not self.is_valid_grid(next_point_grid):
                return None # reached end of the world without finding any walls

            if self.wall_on(next_point_grid):
                return next_point
            
            # This intersection point does not belong to a wall, proceed to next
            last_point = next_point

        
        assert 0, "Should not reach this point!"


if __name__ == '__main__':

    class PointOfView:
        def __init__(self, x=0, y=0, angle=0):
            self.x = x
            self.y = y
            self.angle = angle
            
        def turn_left(self, n):
            self.angle += n
            if self.angle > 359: self.angle = self.angle % 360

        def turn_right(self, n):
            self.angle -= n
            if self.angle < 0: self.angle = 360 - (abs(self.angle) % 360) #remainder behaviour is erratic with negative

        def walk_forward(self, n):
            self.x += n * math.cos(math.radians(self.angle))
            self.y -= n * math.sin(math.radians(self.angle))

        def walk_backward(self, n):
            self.x -= n * math.cos(math.radians(self.angle))
            self.y += n * math.sin(math.radians(self.angle))


    screen = None
    #screenwidth = 320
    #screenheight = 200
    screenwidth = 640
    screenheight = 480
    screenflags = 0
    #screenflags = pygame.FULLSCREEN
    screenbpp = 32

    fwspeed = int(640 / 100 * 2)
    turnspeed = int(640 / 200)

    # TESTING CODE
    def handle_input():
        for e in pygame.event.get():
            if e.type == pygame.QUIT:
                return False
            elif e.type == pygame.KEYDOWN:
                if e.key == pygame.K_ESCAPE:
                    return False
                elif e.key == pygame.K_LEFT:
                    pov.turn_left(2)
                elif e.key == pygame.K_RIGHT:
                    pov.turn_right(2)
                elif e.key == pygame.K_UP:
                    pov.walk_forward(3)
                elif e.key == pygame.K_DOWN:
                    pov.walk_backward(3)
        pygame.event.pump()
        
        keys = pygame.key.get_pressed()
        if keys[pygame.K_UP]:
            pov.walk_forward(fwspeed)
        if keys[pygame.K_LEFT]:
            pov.turn_left(turnspeed)
        if keys[pygame.K_RIGHT]:
            pov.turn_right(turnspeed)
        if keys[pygame.K_DOWN]:
            pov.walk_backward(fwspeed)
            
        return True



    print "Debugging session for Raycaster module."
        
    Renderer = RendererClass(screenwidth, screenheight)

    pygame.init()

    try:
        screen = pygame.display.set_mode((screenwidth, screenheight), screenflags , screenbpp) 
    except pygame.error, msg:   
        print "Error: failed to initialize display -", msg
     
    pygame.display.set_caption('Alien Xenocide - Ray Caster Demo')


    # OK - These LOOK as if the code is ok IF YOU USE THE MINUS
    #pov = PointOfView(Renderer.CUBE_SIZE*1.1, Renderer.CUBE_SIZE*2.1, 45) # player's point of view
    pov = PointOfView(Renderer.CUBE_SIZE*1.5, Renderer.CUBE_SIZE*2.5, 65) # player's point of view

    #error020609-2320 - There still seems to be an error with the vertical intersection, examine the sign of the tangent for Ya
    #pov = PointOfView(Renderer.CUBE_SIZE*2, Renderer.CUBE_SIZE*2, 135) # player's point of view
    #pov = PointOfView(Renderer.CUBE_SIZE*2+20, Renderer.CUBE_SIZE*2+20, 135) # player's point of view

    #error0706092023-DEBUGGING
    #pov = PointOfView(Renderer.CUBE_SIZE*1.5, Renderer.CUBE_SIZE*1.5, 45)
    #pov = PointOfView(Renderer.CUBE_SIZE*1.5, Renderer.CUBE_SIZE*1.5, 340) #*******(LAST ANALYZED)!


    # When accessing the world matrix use: world[y][x]
    # It may look as if it is backwards but y is the matrix line and x is the matrix column
    ##world = [[1,1,1,1],
    ##         [1,0,0,1],
    ##         [1,0,0,1],
    ##         [1,1,1,1]]

    #world = [[1,1,1,1,1,1,1],
    #         [1,0,0,0,0,0,1],
    #         [1,0,0,0,0,0,1],
    #         [1,0,0,0,0,0,1],
    #         [1,0,0,0,0,0,1],
    #         [1,0,0,0,0,0,1],
    #         [1,1,1,1,1,1,1]]

    world = [[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
             [1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1],
             [1,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,0,0,0,1],
             [1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,1],
             [1,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,1,0,0,0,1],
             [1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,1,0,0,0,1],
             [1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,1],
             [1,0,0,0,0,0,0,0,0,0,1,1,1,0,1,0,0,0,0,0,1],
             [1,0,0,0,0,0,0,0,0,0,1,0,1,0,1,0,0,0,0,0,1],
             [1,0,0,0,0,1,1,1,1,1,1,0,1,0,1,0,0,1,1,1,1],
             [1,0,0,0,0,1,0,1,0,1,0,0,1,0,1,0,0,1,0,0,1],
             [1,0,0,0,0,1,0,0,0,0,0,0,1,1,1,0,0,1,1,1,1],
             [1,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1],
             [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]]

    Renderer.load_world(world)
    Renderer.toggle_grid_surface(True) # set Renderer to draw the 2D grid every frame with the walls hit
    Renderer.toggle_ray_debug_info(True) # set Renderer to generate ray debug information

    class FPS_counter:
        def __init__(self):
            self.frames = 0
        def average(self):
            return self.frames / (pygame.time.get_ticks() / 1000.)

    FPS = FPS_counter()
    myfont = pygame.font.SysFont("courier new", 14, False, False)


    while handle_input():
        screen.fill((0, 0, 0)) #clear screen
        Renderer.render_scene(screen, pov)
        #if Renderer.grid_surface_enabled: screen.blit(Renderer.grid_surface, (0,0))

        #DEBUG
        fpstext = myfont.render("FPS: %d" % FPS.average(), False, (0,255,0))
        angletext = myfont.render("ANGLE: %d" % pov.angle, False, (0,255,0))
        screen.blit(fpstext, (screenwidth - 70, 10))
        screen.blit(angletext, (screenwidth - 70, 25))
        pygame.display.flip()
        FPS.frames += 1
        #pygame.time.wait(10)
        

    # Save debug information
    debugf = open("debugf.txt", 'w')
    debugf.write(Renderer.rays_info)
    debugf.close()
    if os.name == 'nt':
        pygame.image.save(Renderer.grid_surface, "lastgridshot.png")
        os.system("start mspaint lastgridshot.png")
        os.system("start notepad debugf.txt")
    else:
        pygame.image.save(Renderer.grid_surface, "lastgridshot.tga")
        os.system("gimp lastgridshot.tga&")
        os.system("kedit debugf.txt&")
        
        
    pygame.quit()

    print "Thanks for playing Alien Xenocide."
